Field of the Invention
This invention relates to memory management, and more specifically to apparatus and methods for incrementally unloading classes using a region-based garbage collector.
Background of the Invention
In an object-oriented managed runtime, such as the Java Virtual Machine (JVM), Microsoft Common Language Runtime (CLR), or Smalltalk runtime, the primary memory resource is a garbage-collected object heap. The object heap provides memory for objects, each of which is an instance of a class. All managed runtimes support object garbage collection. Some managed runtimes, such as the Java Virtual Machine, also provide class garbage collection.
In Java, classes are collected at the granularity of the Java ClassLoader, essentially arbitrary groups of related classes designated by the programmer. A class loader may be garbage collected once there are (a) no references to the class loader, (b) no references to any of its defined classes, (c) no running methods from any defined class on any stack, and (d) no instances of any of its defined classes. Cases (a) and (b) are relatively simple to determine, since class loaders and classes both have proxy objects representing them. The usual garbage collector algorithms will find references to these “for free.” Case (c) is also easy to determine, as stacks must be crawled at the beginning of each garbage collection cycle. Case (d), however, is more difficult to determine.
In a simple implementation, a garbage collector must examine every live object to determine which classes have live instances. This is simple enough to do when the collector is performing a global collection. But modern garbage collectors tend to be incremental in order to deliver superior pause times. Such collectors only examine part of the heap. These collectors typically use a “remembered set” to keep track of references from objects outside of the collection set to objects within the collection set. A naive class unloading garbage collector might use the same solution. However, this is clearly impractical. A remembered set succeeds because most objects tend to have very few references. But every object has a class pointer; remembering each of these would be impractical.
Another naive solution is to use “reference counting.” This solution has several obvious drawbacks. This solution involves incrementing a counter in the class on each allocation, and decrementing it each time an object is reclaimed. Although this solution isn't prone to the typical reference counting problem of circular references, it does have two critical problems. Firstly, it doesn't parallelize well, as it requires all allocating threads to update a shared counter. Secondly, it requires that all reclaimed objects be examined, something that modern garbage collectors work hard to avoid.
Another solution for this problem is to use a train-algorithm-based collector. Such a collector is a region-based collector. However, unlike a generalized region-based collector, it is restricted in that it must collect regions in round-robin order. Due to this restriction, the train algorithm need only remember references from higher numbered to lower numbered regions. In order to enable incremental class unloading, this solution adds a “youngest train” identifier to each class, which records the lowest numbered region which has instances of the class. This simple solution is suitable for the train algorithm, but cannot be applied to nor easily generalized to a general region-based garbage collector.
In view of the foregoing, what are needed are apparatus and methods to efficiently unload classes from any subset of regions in a garbage-collected object heap. Ideally, such apparatus and methods would not require that regions be garbage collected in any particular order.